# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from collections import deque
from typing import List

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None

        q = deque()
        for node in lists:
            q.append(node)

        while True:
            first = q.popleft()
            try:
                second = q.popleft()
                new = self.__mergeTwoLists(first, second)
                q.append(new)
            except IndexError as err:
                return first

    def __mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        gen = self.__findMin(l1, l2)
        result, curr = None, None
        while True:
            try:
                v = next(gen)
                if curr == None:
                    curr = v
                    result = curr
                else:
                    curr.next = v
                    curr = curr.next
            except StopIteration:
                return result


    def __findMin(self, l1: ListNode, l2: ListNode) -> ListNode:
        li1, li2 = l1, l2
        while True:
            if li1 == None and li2 == None:
                return
            elif li1 == None:
                yield li2
                li2 = li2.next
            elif li2 == None:
                yield li1
                li1 = li1.next
            elif li1.val < li2.val:
                yield li1
                li1 = li1.next
            else:
                yield li2
                li2 = li2.next